#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
//#include<string>
using namespace std;

void shellsort(int* a,int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 2;
		int i = 0;
		for (i = 0; i < n-gap; i++)
		{
			int j = i + gap;
			if (a[j] < a[i])
			{
				swap(a[i], a[j]);
			}
		}
	}
}


int main()
{
	int a[10] = { 9,6,3,5,6,1,3,8,6,4};
	int n = 10;
	shellsort(a, n);
	for (auto e : a)
	{
		cout << e << endl;
	}
	
	return 0;
}